package binaryTree;

import org.junit.Test;

import java.util.HashMap;
import java.util.LinkedList;

//二叉树的最大宽度问题
public class LeetCode_662 {

    //定义二叉树节点
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public int widthOfBinaryTree(TreeNode root) {
        return solution_1(root);
    }

    @Test
    public void test(){
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(5);
        root.left.left.left = new TreeNode(6);
//        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(9);
        root.right.right.left = new TreeNode(7);
        //new Utils().treePrint(root);
        System.out.println(widthOfBinaryTree(root));
    }

    /**
     * 求解二叉树的最大宽度，方法：利用指针
     * @param root 二叉树的根节点
     * @return 最大宽度
     */
    public int solution_1(TreeNode root){
        //1. 定义
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        HashMap<TreeNode, Integer> map = new HashMap<>();
        map.put(root,1);
        int maxWidth = -1;
        TreeNode startNode=root, lastNode=root,nextLastNode=null;
        //2. 准备
        if(root==null){
            return 0;
        }else {
            queue.add(root);
        }
        //3. 循环
        while (!queue.isEmpty()){
             TreeNode currentNode = queue.pop();
             int index = map.get(currentNode);
             if(currentNode.left!=null){
                 queue.add(currentNode.left);
                 map.put(currentNode.left,2*index);
                 nextLastNode=currentNode.left;
             }
             if(currentNode.right!=null){
                 queue.add(currentNode.right);
                 map.put(currentNode.right,2*index+1);
                 nextLastNode=currentNode.right;
             }
             if (currentNode == lastNode){
                 maxWidth = Math.max(maxWidth, index-map.get(startNode)+1);
                 if (queue.size() > 0){
                     startNode = queue.get(0);
                 }
                 lastNode = nextLastNode;
             }

        }


        return maxWidth;
    }



}
